package com.lagou.work;

/**
 * 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不 同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘；
 * 有的金矿储量是200kg黄金，需要3个工人 来挖掘…… 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，
 * 不能派出一半人挖取一半的金矿。要 求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
 *
 * 这就是一个0 1背包问题：背包的总数为 10
 *
 * 有五个矿，每个矿需要的人按照矿的重量来决定
 */
public class workTwo {

    public static void main(String[] args) {
        int max = 10;
        int n = 4;
        int[] values = {200,500,300,300,100};
        int[] weights = {3,5,4,4,2};
        int [] x ={0,0,0,0,0,0};   //保存是否拿该物品 0 表示不拿，1表表示拿

        //dp数组  dp[i-1]  i从1开始
        int[][] dp=new int[values.length+1][max+1];

        for(int i=1;i<=values.length;i++){
            for(int j=1;j<=max;j++){
                //选择的物品超过最大承重
                if(weights[i-1]>j){
                    //不能选该物品 等于上轮的最大价值
                    dp[i][j]=dp[i-1][j];
                }
                //选择的物品不超过最大承重
                else{
                    //上轮的最大价值
                    int proValue=dp[i-1][j];
                    //选择该商品后的最大价值
                    int curValue=values[i-1]+dp[i-1][j-weights[i-1]];
                    //两者取最大值
                    dp[i][j]=Math.max(proValue,curValue);
                }

            }
        }

        System.out.println("挖掘最多的金矿为："+dp[values.length][max]);



      /*  for(int i =1 ;i < values.length;i++){

            for(int j = 1; j < max+1; j++){
                System.out.print(dp[i][j] + " ");
            }

            System.out.println();
        }*/

        for(int i=n;i>1;i--)
        {
            if(dp[i][max]==dp[i-1][max])
                x[i]=0;
            else
            {
                x[i]=1;
                max-=weights[i];
            }
        }
        x[1]=(dp[1][max]>0)?1:0;

        for (int i = 1; i < x.length;i++) {
            System.out.print(x[i]);
        }

    }
}
